package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 12
 * Time:14:39
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/***
 * 从上到下打印二叉树
 * 从上到下哎打印出二叉树的每个节点，同一层的节点按照从左到右的熟悉怒打印；
 *
 * 解题思路——使用队列实现
 * 每次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放入到一个队列的末尾；
 * 然后从队列的头部取出最早进入队列的节点，重复前面的打印操作，直至队列中的所有节点都被打印出来；
 */
public class Test9 {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();//存放TreeNode
        queue.add(root);
        while(!queue.isEmpty()){
            //取出对头元素
            TreeNode node = queue.poll();
            //将对头节点的左右子节点入队
            if(root.left != null){
                queue.add(node.left);
            }
            if(root.right != null){
                queue.add(node.right);
            }
            list.add(node.val);

        }
        return list;
    }
}
